package ShuJuJieGou;
import java.util.Scanner;

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListMerger {
    private Node head;

    // Add node to the end of the list
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Print the linked list
    public static String printList(Node node) {
        StringBuilder sb = new StringBuilder();
        while (node != null) {
            sb.append(node.data);
            sb.append("->");
            node = node.next;
        }
        sb.append("nullptr");
        return sb.toString();
    }

    // Merge two sorted lists in ascending order
    public static Node mergeSortedLists(Node l1, Node l2) {
        Node dummy = new Node(0);
        Node tail = dummy;

        while (l1 != null && l2 != null) {
            if (l1.data <= l2.data) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }

        if (l1 != null) {
            tail.next = l1;
        } else {
            tail.next = l2;
        }

        return dummy.next;
    }

    // Reverse a linked list
    public static Node reverseList(Node head) {
        Node prev = null;
        Node current = head;
        Node next = null;

        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        return prev;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("本程序为【将两个不带头结点的递增有序单链表（数据元素为整数）合并为递减有序单链表】的算法测试程序");
        System.out.println();

        // Create first linked list
        System.out.print("请输入 链表1 的结点个数: ");
        int n1 = scanner.nextInt();
        LinkedListMerger list1 = new LinkedListMerger();
        for (int i = 0; i < n1; i++) {
            System.out.print("请输入 链表1 的第 " + (i + 1) + " 个结点的值: ");
            int value = scanner.nextInt();
            list1.append(value);
        }

        // Create second linked list
        System.out.print("请输入 链表2 的结点个数: ");
        int n2 = scanner.nextInt();
        LinkedListMerger list2 = new LinkedListMerger();
        for (int i = 0; i < n2; i++) {
            System.out.print("请输入 链表2 的第 " + (i + 1) + " 个结点的值: ");
            int value = scanner.nextInt();
            list2.append(value);
        }

        // Print original lists
        System.out.println();
        System.out.println("链表1：" + printList(list1.head));
        System.out.println("链表2：" + printList(list2.head));
        System.out.println();

        // Merge in ascending order
        Node mergedAscending = mergeSortedLists(list1.head, list2.head);
        System.out.println("合并链表1和链表2：" + printList(mergedAscending));

        // Reverse to get descending order
        Node mergedDescending = reverseList(mergedAscending);
        System.out.println("合并链表1和链表2并将其逆序：" + printList(mergedDescending));
    }
}